Polar codes, proposed by Arikan [1], are the first class of constructive coding schemes that are provable to achieve the symmetric capacity of the binary-input discrete memoryless channels under a low-complexity Successive Cancellation (SC) decoder. However, the finite-length performance of polar codes under SC is not competitive compared to other modern channel coding schemes such as Low-Density Parity-Check (LDPC) codes and turbo codes. Later, SC List (SCL) decoder is proposed in [2], which can approach the performance of optimal Maximum-Likelihood (ML) decoder. By concatenating a simple Cyclic Redundancy Check (CRC) coding, it was shown that the performance of concatenated polar code is competitive with that of well-optimized LDPC and turbo codes. As a result, polar codes are being considered as a candidate for future Fifth Generation (5G) wireless communication systems.
The main idea of polar coding is to transform a pair of identical binary-input channels into two distinct channels of different qualities, one better and one worse than the original binary-input channel. By repeating such a pair-wise polarizing operation on a set of 2M independent uses of a binary-input channel, a set of 2M “bit-channels” of varying qualities can be obtained. Some of these bit channels are nearly perfect (i.e., error free) while the rest of them are nearly useless (i.e., totally noisy). The point is to use the nearly perfect channel to transmit data to the receiver while setting the input to the useless channels to have fixed or frozen values (e.g., 0) known to the receiver. For this reason, those input bits to the nearly useless and the nearly perfect channel are commonly referred to as frozen bits and non-frozen (or information) bits, respectively. Only the non-frozen bits are used to carry data in a polar code. Loading the data into the proper information bit locations has direct impact on the performance of a polar code. An illustration of the structure of a length 8 polar code is illustrated in FIG. 1.
FIG. 2 illustrates the labeling of the intermediate information bits sl,i, where l∈{0, 1, . . . , n} and i∈{0, 1, . . . , N−1} during polar encoding with N=8. The intermediate information bits are related by the following equation:
            s                        l          +          1                ,        i              =                  s                  l          ,          i                    ⊕              s                  l          ,                      i            +                          2              l                                            ,            if      ⁢                          ⁢              mod        ⁡                  (                                    ⌊                              i                                  2                  l                                            ⌋                        ,            2                    )                      =    0    ,          ⁢            s                        l          +          1                ,        i              =          s              l        ,        i              ,            if      ⁢                          ⁢              mod        ⁡                  (                                    ⌊                              i                                  2                  l                                            ⌋                        ,            2                    )                      =    1  for i∈{0, 1, . . . , N−1} and l∈{0, 1, . . . , n−1}, with s0,i≡ui as the info bits, and sn,i≡xi as the code bits, for i∈{0, 1, . . . , N−1}.